# coding=utf-8
import sys;
class SVMClassifier:
    def __init__(self,dataset,C,KernelType='LINEAR',paraList=None):
        """
            初始化分类器
        """ 
        #样本集对象
        self.__data = dataset;
        #样本规格
        self.__dataSize = [dataset.getRow(),dataset.getCol()];
        #样本最大数目
        self.__MAXROW = 20000;
        
        #核函数类型
        self.__kerType = KernelType;
        #核函数参数列表
        self.__paraList = paraList;
        
        #分类器alpha参数取值的上限
        self.__C = C;
        #分裂器alpha参数向量
        self.__alphaVector = [0.001]*self.__dataSize[0];
        #分类器阈值
        self.__threshold = 0.0;
        
        #共用常量，最小数据间隔
        self.__TINNYGAP = 0.000001;
        
        
        #核函数缓存文件名
        self.__cacheName = "cache.csv";
        #如果样本的数目大于self.__MAXROW，需要创建缓存文件来存储核函数矩阵
        if(self.__dataSize[0]<=self.__MAXROW):
            #在内存中生成核函数矩阵
            self.__kernelMatrixCache = self.__calculateKernelMatrix();
        else:
            try:
                #在磁盘上创建核函数矩阵缓存文件
                self.__kernelMatrixCache = open(self.__cacheName,'w');
                self.__calculateKernelMatrix();
                
            except Exception,e:
                print "创建缓存文件失败",e;
                sys.exit();
    
    def __del__(self):
        """
            删除类对象
        """
        if(type(self.__kernelMatrixCache)!=type([])):
            self.__kernelMatrixCache.close();
        
        

    def trainSVMClassifier(self):
        """
            训练SVM分类器
        """
        rate = 100;
        valueTarget = -30000;
        valueTargetNew = self.__calculateTargetValue(self.__alphaVector);
        while(abs(rate)>self.__TINNYGAP):
            for i in range(self.__dataSize[0]-1):
                for j in range(i+1,self.__dataSize[0]):
                    #select feature index
                    self.__optimizeTwoVariables(i,j);
                   
            valueTarget = valueTargetNew;
            valueTargetNew = self.__calculateTargetValue(self.__alphaVector);
            
            rate = (valueTarget - valueTargetNew)/valueTarget;
        
        #Calculate b;
        self.__threshold = self.__calculateThreshold();
        
    def applySVMClassifier(self,entry):
        """
            将已经完成训练的分类器用于对entry的分类
        """
        sumPart = 0;
        if(len(entry)!=self.__dataSize[1]):
            return "样本的长度错误";
        
        for i in range(self.__dataSize[0]):
            entryA = self.__data.getEntry(i+1);
            sumPart = sumPart + self.__alphaVector[i]*self.__data.getClass(i+1)*self.__calculateKernelInnerProduct(entryA, entry);
        res = sumPart - self.__threshold;
        if(res < 0):
            return -1;
        else:
            return 1;
    def showAlphaVector(self):
        """
            输出alpha参数向量
        """
        print "alpha参数向量为:";
        print self.__alphaVector;
        return self.__alphaVector;
    def showThreshold(self):
        """
            输出分类器的阈值
        """
        print "阈值为:";
        print self.__threshold;
        
    def __calculateThreshold(self):
        """
            计算分类器的阈值
        """
        indexPos = -1;
        indexNeg = -1;
        for i in range(self.__dataSize[0]):
            alpha = self.__alphaVector[i];
            if((alpha>0)&(alpha < self.__C)):
                if((self.__data.getClass(i+1)==1)&(indexPos==-1)):
                    indexPos = i;
                if((self.__data.getClass(i+1)==-1)&(indexNeg==-1)):
                    indexNeg = i;
        
        sumPos = 0.0;
        sumNeg = 0.0;
        for i in range(self.__dataSize[0]):
            sumPos = sumPos + 1.0*self.__alphaVector[i]*self.__data.getClass(i+1)*self.__getKernelMatrix(i, indexPos);
            sumNeg = sumNeg + 1.0*self.__alphaVector[i]*self.__data.getClass(i+1)*self.__getKernelMatrix(i, indexNeg);
        
        return (sumPos + sumNeg)*1.0/2.0      
    def __optimizeTwoVariables(self,s,t):
        """
            选择第s和第t个alpha参数进行优化
        """
        Sst = self.__data.getClass(s+1)*self.__data.getClass(t+1);
        eta = self.__getKernelMatrix(s,s)+self.__getKernelMatrix(t,t)-2.0*self.__getKernelMatrix(s,t);
        sLow = max(0,self.__alphaVector[s]+Sst*self.__alphaVector[t]-(1.0/2.0)*(Sst+1)*self.__C);
        sHigh = min(self.__C,self.__alphaVector[s]+Sst*self.__alphaVector[t]-(1.0/2.0)*(Sst-1.0)*self.__C);
        
        sumPart = 0;
        for i in range(self.__dataSize[0]):
            if((i!=s)&(i!=t)):
                a = self.__alphaVector[i]*self.__data.getClass(i+1)*self.__data.getClass(s+1);
                sumPart = sumPart +a*(self.__getKernelMatrix(t,t)-self.__getKernelMatrix(s,t)+self.__getKernelMatrix(s,i)-self.__getKernelMatrix(t,i));
        
        leftPart = 1-Sst-sumPart;
        
        if(eta > 0):
            alph_s = leftPart*1.0/eta;

        else:###当二阶导数为0时，该最优化问题退化为线性规划。此处只需要计算边界点就可。
            tLow = self.__alphaVector[t]+Sst*(self.__alphaVector[s]-sLow);
            tHigh = self.__alphaVector[t]+Sst*(self.__alphaVector[s]-sHigh);
            pointLowAlph = self.__alphaVector;
            pointLowAlph[s] = sLow;
            pointLowAlph[t] = tLow;
            pointHighAlph = self.__alphaVector;
            pointHighAlph[s] = sHigh;
            pointHighAlph[t] = tHigh;
            
            
            valueLowPoint = self.__calculateTargetValue(pointLowAlph);
            valueHighPoint = self.__calculateTargetValue(pointHighAlph);
            
            if(valueLowPoint < valueHighPoint):
                alph_s = sLow;
            else:
                if(valueLowPoint > valueHighPoint):
                    alph_s = sHigh;
                else:
                    alph_s = self.__alphaVector[s];
                    
                    
        if(alph_s >= sHigh):
            alph_s = sHigh;
        else:
            if(alph_s<=sLow):
                alph_s = sLow;

        alph_t = self.__alphaVector[t]+Sst*(self.__alphaVector[s]-alph_s);
        
        self.__alphaVector[t]=alph_t;
        self.__alphaVector[s]=alph_s; 
    def __calculateTargetValue(self,alphaVector):
        """
            在alpha取值为alphaVector的情况下，计算目标函数的值
        """
        sumQuad = 0;
        sumLinear = 0;
        if(len(alphaVector)!=self.__dataSize[0]):
            return "alphaVector的长度有误";
        
        for i in range(self.__dataSize[0]):
            sumLinear = sumLinear + self.__alphaVector[i];
            for j in range(self.__dataSize[0]):
                sumVec = alphaVector[i]*alphaVector[j]*self.__data.getClass(i+1)*self.__data.getClass(j+1);
                sumQuad = sumQuad + sumVec*self.__getKernelMatrix(i, j);

        return (1.0/2)*sumQuad-sumLinear;
    def __getKernelMatrix(self,s,t):
        """
            获取第s和第t位置的核函数矩阵的值（从0开始）
        """
        if(self.__dataSize[0]<=self.__MAXROW):
            #从内存中获取核函数矩阵的值
            if(s<=t):
                return self.__kernelMatrixCache[s][t-s];
            else:
                return self.__kernelMatrixCache[t][s-t];
        else:
            #从缓存中获取核函数矩阵的值???待添加
            return None;
    
    def __calculateKernelMatrix(self):
        """
            计算核函数矩阵。
            1、根据样本大小决定矩阵存放的位置
            2、在内存中存放的矩阵，按照上三角的方式存储[[A00,A01,A02,A03],[A11,A12,A13],[A22,A23],[A33]]
        """
        if(self.__dataSize[0]<=self.__MAXROW):
            #如果样本个数小于20000就在内存中存放核函数矩阵
            kernelMatrix = [];
            for i in range(self.__dataSize[0]):
                kernelEntry = [];
                for j in range(i,self.__dataSize[0]):
                    entryI = self.__data.getEntry(i+1);
                    entryJ = self.__data.getEntry(j+1);
                    kernelEntry.append(self.__calculateKernelInnerProduct(entryI, entryJ));
                kernelMatrix.append(kernelEntry);
            return kernelMatrix;
        else:
            #如果样本个数大于20000需要在磁盘上存放核函数矩阵???待添加
            return None;
    

    
    def __calculateKernelInnerProduct(self,entryA,entryB):
        """
            计算entryA和entryB两个样本向量的核函数内积
        """
        innerProduct = 0;
        if(self.__kerType == 'LINEAR'):
            for k in range(self.__dataSize[1]):
                innerProduct = innerProduct + entryA[k]*entryB[k];
            return innerProduct;
        if(self.__kerType == 'POLOY'):
            for k in range(self.__dataSize[1]):
                innerProduct = innerProduct + entryA[k]*entryB[k];
            return (innerProduct+1)**self.__paraList[0];
    

        
